#include <iostream>
using namespace std;

//https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* newhead = new ListNode(0);
        ListNode* cur = head;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }
        cur = newhead->next;
        delete newhead;
            return cur;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        head1 = reverse(head1);
        head2 = reverse(head2);

        int t = 0;
        ListNode* cur1 = head1, * cur2 = head2;
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            prev = prev->next = new ListNode(t % 10);
            t /= 10;
        }

        cur1 = ret->next;
        ret->next = nullptr;
        delete ret;
        return reverse(cur1);
    }
};

void test01()
{
    ListNode n1(9);
    ListNode n2(3);
    ListNode n3(7);
    ListNode n4(6);
    ListNode n5(3);
    ListNode n0(0);

    n1.next = &n2;
    n2.next = &n3;

    n4.next = &n5;

    Solution sl;

    auto ret = sl.addInList(&n0, &n4);


    cout << ret->val;
}

int main()
{
    test01();
    return 0;
}